ตูฮาเชฟสกี เกิดที่อะเลคซันดรอฟสโคเย เขตซาโฟนอฟสกี (ปัจจุบันคือ แคว้นสโมเลนสค์ ประเทศรัสเซีย) ในครอบครัวยากจนที่มีเชื้อสายขุนนาง[5] ตามเรื่องเล่าระบุว่าครอบครัวของเขาสืบเชื้อสายมาจากเคานต์ชาวเฟลมิชซึ่งติดค้างอยู่ที่เขตตะวันออกในช่วงสงครามครูเสดและพาภรรยาชาวตุรกีเข้ามาตั้งถิ่นฐานในรัสเซีย[6][7] ปู่ทวดของเขาอะเลคซันดร์ ตูฮาเชฟสกี (ค.ศ. 1793–1831) ทำหน้าที่เป็นพันเอกในกองทัพจักรวรรดิรัสเซีย เขามีเชื้อสายรัสเซีย[8] หลังจากเรียนที่โรงเรียนทหารมอสโกใน ค.ศ. 1912 เขาย้ายไปเรียนที่โรงเรียนการทหารอะเลคซันดรอฟสโคเย และจบการศึกษาใน ค.ศ. 1914 เมื่อเริ่มสงครามโลกครั้งที่หนึ่ง เขาเข้าร่วมกับกรมทหารเซมิออนอฟสกี (กรกฎาคม ค.ศ. 1914) โดยขณะนั้นเขาดำรงยศร้อยตรีและได้พูดว่า:

"ผมเชื่อว่าสิ่งที่จำเป็นเพื่อให้บรรลุสิ่งที่ผมต้องการมีเพียงความกล้าหาญและความมั่นใจในตนเองเท่านั้น แน่นอนผมมีความมั่นใจในตัวเองเพียงพอ ... ผมบอกกับตัวเองว่าผมจะเป็นนายพลตอนสามสิบหรือจนผมจะไม่มีชีวิตอยู่ถึงตอนนั้น"[9]

เมื่อถูกกองทัพจักรวรรดิเยอรมันจับเป็นเชลยในเดือนกุมภาพันธ์ ค.ศ. 1915 ตูฮาเชฟสกีหลบหนีออกจากค่ายเชลยศึกสี่ครั้ง ตูฮาเชฟสกีหลบหนีออกจากค่ายเชลยศึกสี่ครั้ง และที่สุดก็ถูกกุมตัวเป็นผู้พยายามหลบหนีซ้ำ ๆ ไว้ที่ป้อมอิงก็อลชตัทในบาวาเรีย[10] ณ ที่นั้น เขาอยู่ห้องขังเดียวกับชาร์ล เดอ โกลล์ ผู้บันทึกไว้ว่า ตูฮาเชฟสกีนำไวโอลินของโกลล์มาบรรเลง พล่ามความเชื่อแบบนิยมการทำลายล้าง และพูดจาต่อต้านชาวยิวซึ่งตูฮาเชฟสกีเรียกว่า เป็นสุนัขที่ "แพร่เห็บหมัดของตัวเองไปทั้งโลก"[11]

การหลบหนีครั้งที่ห้าของตูฮาเชฟสกีเป็นผลสำเร็จ เมื่อข้ามผ่านชายแดนสวิตเซอร์แลนด์–เยอรมนีแล้ว เขากลับถึงรัสเซียในเดือนกันยายน ค.ศ. 1917 และภายหลังการปฏิวัติเดือนตุลาคม ค.ศ. 1917 ตูฮาเชฟสกีเข้าร่วมบอลเชวิค และได้มีบทบาทสำคัญในกองทัพแดง แม้จะมีเชื้อสายขุนนาง